package com.hy.study.hashtable;

import java.util.List;
import java.util.Scanner;

/**
 * Hash表
 */
public class HashTableDemo {

    public static void main(String[] args) {
        HashTable hashTable = new HashTable(7);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("----请选择------");
            System.out.printf("add:添加\t list: 显示\t exit: 退出 \t find: 查找 \t delete: 删除\n");
            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("输入ID:");
                    int id = scanner.nextInt();
                    System.out.println("输入名字:");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTable.add(emp);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                case "find":
                    System.out.println("请输入要查找的ID:");
                     id=scanner.nextInt();
                    Emp emp1 = hashTable.find(id);
                    System.out.println("查询到用户:"+emp1);
                    break;
                case "delete":
                    System.out.println("请输入删除的ID:");
                    id=scanner.nextInt();
                    hashTable.delete(id);
                    break;

                default:
                    break;
            }
        }
    }
}

/**
 * Hash表用来管理多条链表
 */

class HashTable {
    private EmpLinkedList[] empLinkedListArray;
    private int size;

    public HashTable(int size) {
        this.size = size;
        this.empLinkedListArray = new EmpLinkedList[size];
        //这时候需要分别初始化每个链表
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    public HashTable() {
        this.size = 16;
        this.empLinkedListArray = new EmpLinkedList[16];
    }

    /**
     * 遍历hash表
     */
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }

    }

    /**
     * 根据输入的ID查询
     *
     * @param id
     * @return
     */
    public Emp find(int id) {
        int empLinkedListNo = this.hashFun(id);
        return empLinkedListArray[empLinkedListNo].findEmpById(id);
    }

    /**
     * 从Hashtable 中删除指定的元素
     * @param id
     */
    public void delete(int id){
        int empLinkedListNo = this.hashFun(id);
        empLinkedListArray[empLinkedListNo].delete(id);

    }

    /**
     * Hashtable 添加元素
     *
     * @param emp
     */
    public void add(Emp emp) {
        //计算hash值

        int empLinkedListNo = hashFun(emp.getId());
        empLinkedListArray[empLinkedListNo].add(emp);
    }

    /**
     * Hash 取模法
     *
     * @param id
     * @return
     */
    private int hashFun(int id) {
        return id % size;
    }


}


/**
 * 一条链表
 */
class EmpLinkedList {
    private Emp head;

    /**
     * 添加链表
     *
     * @param emp
     */
    public void add(Emp emp) {
        //如果是添加第一个
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个 需要找到最后一个
        Emp temp = head;
        while (temp == null) {
            temp = temp.getNext();
        }
        temp.setNext(emp);

    }

    /**
     * 通过ID查询雇员信息
     *
     * @param id
     * @return
     */
    public Emp findEmpById(int id) {
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        Emp temp = head;
        boolean flag = false;
        while (temp != null) {
            if (temp.getId() == id) {
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (flag) {
            return temp;
        }

        return null;

    }

    /**
     * 通过ID从链表中删除
     * @param id
     */
    public void delete(int id){
        if(head==null){
            System.out.println("链表为空无法删除");
            return;
        }
        if(head.getId()==id){
            head.setNext(head.getNext());
            return;
        }
        Emp temp=head;
        boolean flag=false;

        while (temp.getNext()!=null){
            if(temp.getNext().getId()==id){
                flag=true;
                break;
            }
            temp=temp.getNext();
        }
        if(flag){
            temp.setNext(temp.getNext().getNext());
        }
    }

    /**
     * 遍历链表
     */
    public void list(int no) {
        if (head == null) {//链表为空
            System.out.println("第" + no + "链表为空");
            return;
        }
        System.out.printf("第" + no + "链表信息为:");
        Emp temp = head;
        while (true) {
            System.out.printf("id->%d name-->%s", temp.getId(), temp.getName());
            if (temp.getNext() == null) {
                break;
            }
            temp = temp.getNext();

        }
        System.out.println();
    }



}

/**
 * 链表元素
 */
class Emp {
    private int id;
    private String name;
    private Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public Emp() {
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Emp getNext() {
        return next;
    }

    public void setNext(Emp next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
